package 回溯;


public class Nqueen {

		public static int num1(int n) {
			if (n < 1) {
				return 0;
			}
			int[] record = new int[n];
			return process1(0, record, n);
		}

		public static int process1(int i, int[] record, int n) {
			if (i == n) {
				return 1;
			}
			int res = 0;
			for (int j = 0; j < n; j++) {
				if (isValid(record, i, j)) {
					record[i] = j;
					res += process1(i + 1, record, n);
				}
			}
			return res;
		}

		public static boolean isValid(int[] record, int i, int j) {
			for (int k = 0; k < i; k++) {
				if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {
					return false;
				}
			}
			return true;
		}

		public static int num2(int n) {
			if (n < 1 || n > 32) {
				return 0;
			}
			int upperLim = n == 32 ? -1 : (1 << n) - 1;
			return process2(upperLim, 0, 0, 0);
		}

		public static int process2(int upperLim, int colLim, int leftDiaLim,
				int rightDiaLim) {
			if (colLim == upperLim) {
				return 1;
			}
			int pos = 0;
			int mostRightOne = 0;
			pos = upperLim & (~(colLim | leftDiaLim | rightDiaLim));
			int res = 0;
			while (pos != 0) {
				mostRightOne = pos & (~pos + 1);
				pos = pos - mostRightOne;
				res += process2(upperLim, colLim | mostRightOne,
						(leftDiaLim | mostRightOne) << 1,
						(rightDiaLim | mostRightOne) >>> 1);
			}
			return res;
		}

		public static void main(String[] args) {
			int n = 15;

			long start = System.currentTimeMillis();
			System.out.println(num2(n));
			long end = System.currentTimeMillis();
			System.out.println("cost time: " + (end - start) + "ms");

			start = System.currentTimeMillis();
			System.out.println(num1(n));
			end = System.currentTimeMillis();
			System.out.println("cost time: " + (end - start) + "ms");

		}

		/*
		 2023/3/15
		 重新写一下, 这个 judge()函数
		 i : row
		 j : colum
		 主要是这个数据的 表示有点让人有点, 迷惑 , 行和列的 本质是什么, 这里要注意一下!
		 */
	   public boolean judge(int i,int j,int nums[]){
		   // 判断 同一列 直接 与下面的判断 合在  一起
//		   for(int k = 0;k < i; k++){
//			   if(nums[k] == j){
//				   return false;
//			   }
//		   }
//
		   // 判断对角线
		   for(int k = 0;k < i;k++){
			   // 正方形, 所以 在对角线上, 就是 斜率 为 1
			   if( nums[k] == j || Math.abs(j - nums[k]) == (i - k)){
				   return false;
			   }
		   }

		   return true;
	   }

	}

